package com.yhk.graph;

import java.util.ArrayList;
import java.util.List;

/**
 * @version 1.0
 * @Author moresuo
 * @Date 2024/10/30 16:50
 * @注释 加权有向图领接表实现
 */
public class WeightedDigraphByList {
    //存储邻接节点和权重
    public static class Edge {
        int to;
        int weight;

        public Edge(int to, int weight) {
            this.to=to;
            this.weight=weight;
        }
    }
    //邻接表
    private List<Edge>[] graph;

    public WeightedDigraphByList(int n) {
        graph = new List[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
    }

    /**
     * 增加一条带权重的有向边
     * @param to
     * @param from
     * @param weight
     */
    public void addEdge(int to, int from, int weight) {
        graph[from].add(new Edge(to, weight));
    }

    /**
     * 删除一条有向边
     * @param from
     * @param to
     */
    public void removeEdge(int from, int to) {
        for (Edge e : graph[from]) {
            if (e.to == to) {
                graph[from].remove(e);
                break;
            }
        }
    }

    /**
     * 判断两个节点是否相邻
     * @param from
     * @param to
     * @return
     */
    public boolean hasEdge(int from, int to) {
        for (Edge e : graph[from]) {
            if (e.to == to) {
                return true;
            }
        }
        return false;
    }

    /**
     * 返回一条边的权重
     * @param from
     * @param to
     * @return
     */
    public int weight(int from, int to) {
        for (Edge e : graph[from]) {
            if (e.to == to) {
                return e.weight;
            }
        }
        throw new IllegalArgumentException("no such edge");
    }

    /**
     * 返回某个节点的所有邻接点
     * @param v
     * @return
     */
    public List<Edge> neighbors(int v) {
        return graph[v];
    }


}
